#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int DataType;

typedef struct {
  DataType* a;
  int top;
  int capacity;
}Stack;

void StackInit(Stack* ps);
void StackDestory(Stack* ps);
void StackPush(Stack* ps, DataType x);
void StackPop(Stack* ps);
bool StackEmpty(Stack* ps);
DataType StackTop(Stack* ps);

void StackInit(Stack* ps)
{
  assert(ps);

  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}
void StackDestory(Stack* ps)
{
  assert(ps);

  if (ps->a != NULL) {
    free(ps->a);
    ps->a = NULL;
  }
  ps->capacity = 0;
  ps->top = 0;
}
void StackPush(Stack* ps, DataType x)
{
  assert(ps);

  if (ps->top == ps->capacity) {
    int newCapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    ps->a = (DataType*)realloc(ps->a, sizeof(DataType) * newCapcity);
    if (ps->a == NULL) {
      printf("realloc error");
      exit(-1);
    }
    ps->capacity = newCapcity;
  }

  ps->a[ps->top] = x;
  ps->top++;
}
void StackPop(Stack* ps)
{
  assert(ps);
  assert(ps->top > 0);

  ps->top--;
}
bool StackEmpty(Stack* ps)
{
  assert(ps);

  return ps->top == 0;
}
DataType StackTop(Stack* ps)
{
  assert(ps);
  assert(ps->top > 0);

  return ps->a[ps->top - 1];
}

int main()
{
  return 0;
}

